import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * (顺序存储)二叉树
 * User: xwl
 * Date: 2023-05-23
 * Time: 8:49
 */
public class Test1 {
    //
    public int[] elem;
    //
    public int usedSize;

    // 构造方法
    public Test1() {
        this.elem = new int[10];
    }

    /**
     * 读入数据
     * @param array:待读入的树的元素
     */
    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    /**
     * 创建堆
     */
    public void createHeap() {
        // 从底部开始向下调整，创建大根堆
        for (int parent = (usedSize - 1 - 1)/2; parent >= 0; parent--) {
            shiftDown(parent,usedSize);
        }
    }

    /**
     * 将树的根节点向下调整，创建大根堆
     * @param parent:树的根节点
     * @param len:调整的长度
     */
    public void shiftDown(int parent, int len) {
        // parent的左孩子
        int child = 2 * parent + 1;
        //
        while(child < len) {
            // 使child指向较大的孩子
            if (child + 1 < len && elem[child] < elem[child+1]) {
                child++;
            }
            // 交换
            if (elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }


    /**
     * 插入后，向上调整
     * @param child:插入的节点的位置
     */
    public void shiftUp(int child) {
        // 父亲节点的位置
        int parent = (child - 1) / 2;
        // 实现
        while (child > 0) {
            if (elem[child] > elem[parent]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }

    /**
     * 插入数据,并保持大根堆
     * @param val:待插入的数据
     */
    public void offer(int val) {
        if (ifFull()) {
            // 扩容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        // 入栈
        elem[usedSize++] = val;
        // 向上调整
        shiftUp(usedSize - 1);
    }

    /**
     * 判断二叉树树是否已满
     * @return true:栈已满 false:未满
     */
    public boolean ifFull() {
        return usedSize == elem.length;
    }

    /**
     * 删除树中节点
     */
    public void pop() {
        // 判断树是否为空
        if (isEmpty()) {
            return;
        }
        //
        swap(0,usedSize - 1);
        usedSize--;
        //
        shiftDown(0,usedSize);
    }

    /**
     * 判断树是否为空
     * @return true: false:
     */
    public boolean isEmpty() {
        return usedSize == 0;
    }

    /**
     * 交换根节点和待删除元素的位置
     * @param rootIndex:根节点的位置
     * @param valIndex:待删除节点的位置
     */
    public void swap(int rootIndex, int valIndex) {
        int tmp = elem[rootIndex];
        elem[rootIndex] = elem[valIndex];
        elem[valIndex] = tmp;
    }

    /**
     * 堆排(大根堆)-从大到小排
     */
    public void heapSort() {
        int end = usedSize - 1;
        while (end > 0) {
            swap(elem[0], elem[end]);
            shiftDown(0, end);
            end--;
        }
    }
}
